package 力扣.题库.未分类;

import java.util.Arrays;
import java.util.Collections;

public class demo_2966 {
	/*
		2966. 划分数组并满足最大差限制
	算术评级: 4
	1396
	
	给你一个长度为 n 的整数数组 nums，以及一个正整数 k 。
	将这个数组划分为 n / 3 个长度为 3 的子数组，并满足以下条件：
	子数组中 任意 两个元素的差必须 小于或等于 k 。
	返回一个 二维数组 ，包含所有的子数组。如果不可能满足条件，就返回一个空数组。如果有多个答案，返回 任意一个 即可。
	
	示例 1：
	输入：nums = [1,3,4,8,7,9,3,5,1], k = 2
	输出：[[1,1,3],[3,4,5],[7,8,9]]
	解释：
	每个数组中任何两个元素之间的差小于或等于 2。
	示例 2：
	输入：nums = [2,4,2,2,5,2], k = 2
	输出：[]
	解释：
	将 nums 划分为 2 个长度为 3 的数组的不同方式有：
	[[2,2,2],[2,4,5]] （及其排列）
	[[2,2,4],[2,2,5]] （及其排列）
	因为有四个 2，所以无论我们如何划分，都会有一个包含元素 2 和 5 的数组。因为 5 - 2 = 3 > k，条件无法被满足，所以没有合法的划分。
	示例 3：
	输入：nums = [4,2,9,8,2,12,7,12,10,5,8,5,5,7,9,2,5,11], k = 14
	输出：[[2,2,12],[4,8,5],[5,9,7],[7,8,5],[5,9,10],[11,12,2]]
	解释：
	每个数组中任何两个元素之间的差小于或等于 14。
	
	提示：
	n == nums.length
	1 <= n <= 105
	n 是 3 的倍数
	1 <= nums[i] <= 105
	1 <= k <= 105
	 */
	
	public int[][] divideArray(int[] nums, int k) {
		/*
		排序后进行切分，判断是符合
		nums = [1,3,4,8,7,9,3,5,1], k = 2
		n = 3
		0~2 3~5 6~8
		 */
		Arrays.sort(nums);
		int n = nums.length / 3;
		int[][] cnt = new int[n][3];
		// 	一共要分为3组 0 ~ n-1  n ~ 2n - 1 2n~3n-1
		for(int i = 0; i < n; i ++) {
			if(nums[3 * i + 2] - nums[3 * i] > k) {
				return  new int[][]{};
			}
			cnt[i] = new int[]{nums[3 * i], nums[3 * i + 1], nums[3 * i + 2]};
		}
		return cnt;
		
	}
}
